package algorithm.dynamicProgramming.leetcode;
//740. 删除并获得点数
public class DeleteAndEarn {
    public static void main(String[] args) {
        int[] data ={2, 2, 3, 3, 3, 4};
        System.out.println(deleteAndEarn(data));

    }

    public static int deleteAndEarn(int[] nums) {

        int max = 0;
        for (int i = 0; i < nums.length; i++) {
             max = Math.max(nums[i],max);
        }
        int[] counts = new int[max+1];

        for (int item:nums){
            counts[item]++;
        }
        int[] f = new int[max+1];
        f[0] = 0;
        f[1] = counts[1];
        for (int i =2;i<=max;i++){
            f[i] = Math.max(f[i-1],f[i-2]+i*counts[i]);
        }

        return f[max];
    }

    public static int deleteAndEarn2(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(nums[i],max);
        }
        int[] counts = new int[max+1];

        for (int item:nums){
            counts[item]++;
        }
        int[][] f = new int[max+1][2];
        f[0][0] = 0;
        f[0][1]=0;
        for (int i = 2; i <= max; i++) {
            f[i][0] = Math.max(f[i-1][0],f[i-1][1]);
            f[i][1] = f[i-1][0]+i*counts[i];
        }
        return Math.max(f[max][0],f[max][1]);
    }
}
